package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * TODO 难点/技巧:
 * - 转化为两个人同时从左上走到右下.
 * - 三位dp数组
 * <p>
 * N*N, 俩人要一起走, 每人需要走2*(N-1)步到达右下
 *
 * @author tzp
 * @since 2020/10/27
 */
public class LC741 implements DynamicProblem {
    public int cherryPickup(int[][] grid) {//N*N
        int N = grid.length;
        if (N == 1) return grid[0][0];
        int[][][] dp = new int[2][N][N];
        //第一维是标志哪个人, 0号选手和1号选手; 第二三维是坐标
        //dp值的含义是俩人同时走x步分别到达对应格子后能拿到的cherry数
        //答案是dp[0][N-1][N-1] + dp[1][N-1][N-1]
        dp[0][0][0] = grid[0][0];
        for (int i = 1; i <= 2 * (N - 1); i++) {
            for (int x = 0; x <= i && x <= N - 1; x++) {
                for (int y = 0; y <= i && y <= N - 1; y++) {
                   //
                }
            }
        }
        return dp[0][N - 1][N - 1] + dp[1][N - 1][N - 1];
    }

    public static void main(String[] args) {
        System.out.println(new LC741());
    }
}
